#
# @lc app=leetcode.cn id=322 lang=python3
#
# [322] 零钱兑换
#

# @lc code=start

"""
解法一：遍历一棵N叉树
Time Limit Exceeded
"""
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        def dp(n):
            if n == 0:
                return 0
            if n < 0:
                return -1

            res = float('INF')
            for coin in coins:
                subproblem = dp(n - coin)
                # 子问题若无解，跳过
                if subproblem == -1:
                    continue
                res = min(res, 1 + subproblem)
            return res if res != float('INF') else -1

        return dp(amount)


# @lc code=end
